home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / nihcl-30.lha / nihcl-3.0 / lib / SortedCltn.c < prev    next >
C/C++ Source or Header  |  1990-05-20  |  6KB  |  230 lines
  1. /* SortedCltn.c -- implementation of sorted collection
  2.  
  3.     THIS SOFTWARE FITS THE DESCRIPTION IN THE U.S. COPYRIGHT ACT OF A
  4.     "UNITED STATES GOVERNMENT WORK".  IT WAS WRITTEN AS A PART OF THE
  5.     AUTHOR'S OFFICIAL DUTIES AS A GOVERNMENT EMPLOYEE.  THIS MEANS IT
  6.     CANNOT BE COPYRIGHTED.  THIS SOFTWARE IS FREELY AVAILABLE TO THE
  7.     PUBLIC FOR USE WITHOUT A COPYRIGHT NOTICE, AND THERE ARE NO
  8.     RESTRICTIONS ON ITS USE, NOW OR SUBSEQUENTLY.
  9.  
  10. Author:
  11.     K. E. Gorlen
  12.     Bg. 12A, Rm. 2033
  13.     Computer Systems Laboratory
  14.     Division of Computer Research and Technology
  15.     National Institutes of Health
  16.     Bethesda, Maryland 20892
  17.     Phone: (301) 496-1111
  18.     uucp: uunet!nih-csl!kgorlen
  19.     Internet: kgorlen@alw.nih.gov
  20.     September, 1985
  21.  
  22. Function:
  23.     
  24. A SortedCltn is a Collection of objects ordered as defined by the
  25. virtual function "compare", which the objects must implement.  The "add"
  26. function locates the position at which to insert the object by
  27. performing a binary search, then invokes the private function
  28. "OrderedCltn::addAtIndex" to insert the object after shifting up all the
  29. objects after it in the array; therefore, a SortedCltn is not efficient
  30. for a large number of objects.
  31.  
  32. $Log:    SortedCltn.c,v $
  33.  * Revision 3.0  90/05/20  16:45:35  kgorlen
  34.  * Release for 1st edition.
  35.  * 
  36. */
  37.  
  38. #include "SortedCltn.h"
  39. #include "nihclIO.h"
  40.  
  41. #define    THIS    SortedCltn
  42. #define    BASE    OrderedCltn
  43. #define BASE_CLASSES BASE::desc()
  44. #define MEMBER_CLASSES
  45. #define VIRTUAL_BASE_CLASSES
  46.  
  47. DEFINE_CLASS(SortedCltn,1,"$Header: /afs/alw.nih.gov/unix/sun4_40c/usr/local/src/nihcl-3.0/share/lib/RCS/SortedCltn.c,v 3.0 90/05/20 16:45:35 kgorlen Rel $",NULL,NULL);
  48.  
  49. SortedCltn::SortedCltn(unsigned size) : BASE(size) {}
  50.  
  51. void SortedCltn::operator=(const SortedCltn& s)
  52. {
  53.     OrderedCltn::operator=(s);
  54. }
  55.  
  56. Object* SortedCltn::add(Object& ob)
  57. {
  58.     if (size()==0) {        // add first object to collection 
  59.         OrderedCltn::add(ob);
  60.         return &ob;
  61.     }
  62.  
  63.     int i = findIndexOf(ob);
  64.  
  65.     if (i == -1 || ob.compare(*contents[i]) != 0)
  66.         OrderedCltn::addAtIndex(i + 1, ob);
  67.     else
  68. //        An object(s) equal to the argument "ob" already exists.
  69. //        Add another one, after the sequence.
  70.         OrderedCltn::addAtIndex(findIndexOfLastKey(ob, i) + 1, ob);
  71.  
  72.     return &ob;
  73. }
  74.     
  75. int SortedCltn::findIndexOf(const Object& key) const
  76. {
  77. //    This algorithm is adapted from Horowitz & Sahni,
  78. //    "Fundamentals of Data Structures", 1976, Section 7.1,
  79. //    algorithm BINSRCH.
  80. //    This function will return (on failure to find):
  81. //        (-1) if the key is less than all other keys; 
  82. //        otherwise, returns i, such that i is the greatest index
  83. //        whose key is less than the key value.
  84. //    On successful search the algorithm returns an index to a
  85. //    key which equals the key argument.  However, this is not
  86. //    guaranteed to be the first key of a sequence, when such a
  87. //    sequence exists.
  88.  
  89.     int l = 0;
  90.     int u = size() - 1;
  91.     int m = 0;
  92.     int c;
  93.  
  94.     if (key.compare(*contents[0]) < 0)
  95.         return -1;
  96.  
  97.     while (l <= u) {
  98.         m = (l + u) >> 1;
  99.         if ((c = key.compare(*contents[m])) > 0)
  100.             l = m + 1;
  101.         else
  102.         if (c == 0)
  103.             return m;
  104.         else
  105.             u = m - 1;
  106.     }
  107.  
  108. //    Binary search will leave the final index searched either
  109. //    just greater than the key or just less than, depending 
  110. //    upon the relation of the search key to the existing
  111. //    collection.  Must adjust here, in case it was placed just
  112. //    to the right.
  113.  
  114.     if (m > 0 && c < 0)
  115.         m--;
  116.  
  117.     return m; // Key not found.
  118. }
  119.  
  120. Object* SortedCltn::addAfter(const Object&, Object& /*newob*/)
  121. {
  122.     shouldNotImplement("addAfter"); return 0;
  123. }
  124.  
  125. Object* SortedCltn::addAllLast(const OrderedCltn&)
  126. {
  127.     shouldNotImplement("addAllLast"); return 0;
  128. }
  129.  
  130. Object* SortedCltn::addBefore(const Object&, Object& /*newob*/)
  131. {
  132.     shouldNotImplement("addBefore"); return 0;
  133. }
  134.  
  135. Object* SortedCltn::addLast(Object&)
  136. {
  137.     shouldNotImplement("addLast"); return 0;
  138. }
  139.  
  140. void SortedCltn::atAllPut(Object&)
  141. {
  142.     shouldNotImplement("atAllPut");
  143. }
  144.  
  145. int SortedCltn::indexOfSubCollection(const SeqCltn& /*cltn*/, int /*start*/) const
  146. {
  147.     shouldNotImplement("indexOfSubCollection"); return 0;
  148. }
  149.  
  150. void SortedCltn::replaceFrom(int /*start*/, int /*stop*/, const SeqCltn& /*replacement*/, int /*startAt*/)
  151. {
  152.     shouldNotImplement("replaceFrom");
  153. }
  154.  
  155. void SortedCltn::sort()
  156. {
  157.     shouldNotImplement("sort");
  158. }
  159.  
  160. SortedCltn Collection::asSortedCltn() const
  161. {
  162.     SortedCltn cltn(MAX(size(),DEFAULT_CAPACITY));
  163.     addContentsTo(cltn);
  164.     return cltn;
  165. }
  166.  
  167. SortedCltn::SortedCltn(OIOin& strm)
  168. :
  169. #ifdef MI
  170.     Object(strm),
  171. #endif
  172.     BASE(strm)
  173. {
  174. }
  175.  
  176. SortedCltn::SortedCltn(OIOifd& fd)
  177. :
  178. #ifdef MI
  179.     Object(fd),
  180. #endif
  181.     BASE(fd)
  182. {
  183. }
  184.  
  185. Range SortedCltn::findRangeOf(const Object& key) const
  186. {
  187.     int i = SortedCltn::findIndexOf(key);
  188.  
  189.     if (i == -1 || key.compare(*contents[i]) != 0)
  190. //        Give the caller the place where "key" should
  191. //        be placed, if not found.
  192.         return Range(i, 0);
  193.     int k = findIndexOfFirstKey(key, i);
  194.     int l = findIndexOfLastKey(key, i);
  195.     return Range(k, l - k + 1);
  196. }
  197.  
  198. int SortedCltn::findIndexOfFirstKey(const Object& key, const int index) const
  199. {
  200.     for (register j = index - 1; j > -1; j--)
  201.         if (key.compare(*contents[j]) != 0)
  202.             break;
  203.     return (j + 1);
  204.  
  205. }
  206.  
  207. int SortedCltn::findIndexOfLastKey(const Object& key, const int index) const
  208. {
  209.     register max = size();
  210.     for (register j = index + 1; j < max; j++)
  211.         if (key.compare(*contents[j]) != 0)
  212.             break;
  213.     return (j - 1);
  214.  
  215. }
  216.  
  217. unsigned SortedCltn::occurrencesOf(const Object& key) const
  218. {
  219.     Range r = findRangeOf(key);
  220.     return unsigned(r.length());
  221. }
  222.  
  223. Object* SortedCltn::remove(const Object& ob)
  224. {
  225.     Range r = findRangeOf(ob);
  226.     int count = r.length();
  227.     if (count == 0) return nil;
  228.     return removeAtIndex(r.firstIndex());
  229. }
  230.